package sort;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 5, 2, 5};
        QuickSort qq = new QuickSort();
        qq.quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }


    public void quickSort(int[] nums){
        sort(nums,0,nums.length - 1);
    }

    public void sort(int[] nums,int left, int right){
        if(left == right) return;

        int partition = partition(nums, left, right);
        if(partition == -1){
            return;
        }
        sort(nums,partition + 1,right);
        sort(nums,left,partition - 1);


    }

    public int partition(int[] nums, int start, int end){
        if(start > end) return -1;
        int base = nums[start];
        int l = start;
        int r = end;
        while (l != r){
            while (l < r && nums[r] > base){
                r--;
            }
            while (l < r && nums[l] <= base){
                l++;
            }
            if (l < r) {
                swap(nums, l, r);
            }
        }
        swap(nums,start,l);
        return l;
    }

    public void swap(int[] nums, int left, int right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }



}
